/*
Date:20210409 21:21pm
key:左缩右缩只存在两种情况，而且相差一个的时候就可以判断了
*/
class Solution {
public:
    int erfen(int L,int R,vector<int>& nums)
    {
        //相差一个的时候就可以判断了
        if(L+1>=R)
        {
            return nums[L]>nums[R]?nums[R]:nums[L];
        }
        else
        {
            
            //int key=nums[ceil((double)(L+R)/2)];
            int key=nums[(L+R)/2];
            //cout<<key;
            if(nums[L]<=key&&nums[L]>nums[R])
            {
                //cout<<"右";
                return erfen((L+R)/2,R,nums);
            }
            if(nums[L]>key&&key<=nums[R])
            {
                //cout<<"左";
                return erfen(L,(L+R)/2,nums);
            }
            //这里一定要有return key，我也不知道为什么
            return key;
        }
    }
    int findMin(vector<int>& nums)
     {
        if(nums.size()==0)
        {
            return 0;
        }
        if(nums.size()==1)
        {
            return nums[0];
        }
        //把头尾相同的排掉
        while(nums[0]==nums[nums.size()-1])
        {
            nums.pop_back();
            if(nums.size()==1)
            {
                return nums[0];
            }
        }
        //如果数组单调递增
        if(nums[0]<nums[nums.size()-1])
        {
            return nums[0];
        }
        return erfen(0,nums.size()-1,nums);
    }
};